package one.stack;

import java.util.Stack;

/**
 * 有效的括号
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 */
public class IsValid {
    //思路：使用栈
    //时间复杂度：O(n)
    public static boolean isValid(String s) {
        Stack stack = new Stack<>();
        for(int i = 0; i < s.length(); i++){
            char c = s.charAt(i);
//            System.out.println(c);
            if(c == '(' || c == '[' || c == '{'){
                stack.push(c);
            }else{
                if(stack.empty()){
                    return false;
                }else{
                    if((c == ')' && (char)stack.peek() != '(') || (c == ']' && (char)stack.peek() != '[') || (c == '}' && (char)stack.peek() != '{')){
                        return false;//注意：应该判断哪些不符合条件，不符合条件返回false。不能判断符合条件的。
                    }
                    stack.pop();//注意：如果匹配成功，左括号应该出栈。
                }
            }
        }
        return stack.empty();//注意：栈最后应该为空。
    }

    public static void main(String[] args) {
        String s = "()";
        boolean valid = isValid(s);
        System.out.println(valid);
    }
}
